package algorithm.dynamic;

/**
 * Leetcode : https://leetcode.com/problems/house-robber/
 * Difficulty : Easy
 *
 * 给一个全部元素大于0整形数组。不能连续取相邻两个数字。求能取得的数字的最大值。
 *
 * 思路：
 * 不能取相邻两个，那就只能是【相隔一个】or【相隔两个】的情况。(如果相隔三个那么其实就是相隔一个的情况)
 * 用动态规划，每一个格子存储以当前点为结束时，所能达到的最大值。
 * 也就是 dp[i] = Max(dp[i-1], dp[i-2]) + nums[i]
 * 然后在过程中求 Max(dp[i]) 即可
 *
 * @Author Antony
 * @Since 2018/11/1 10:52
 */
public class HouseRobber {

    public static void main(String[] args) {
        int[] arr_1 = new int[]{1,2,3,1};
        System.out.println(rob(arr_1));

        int[] arr_2 = new int[]{2,7,9,3,1};
        System.out.println(rob(arr_2));
    }

    /**
     * leetcode : 3ms 100.0%
     * @param nums
     * @return
     */
    public static int rob(int[] nums){
        if(nums.length == 0){
            return 0;
        }
        int max=nums[0];
        int idx1,idx2, tmp1,tmp2, tmpDp;
        for(int i=1; i<nums.length; i++){
            idx1 = i-2;
            idx2 = i-3;
            tmp1 = idx1>=0 ? nums[idx1] : 0;
            tmp2 = idx2>=0 ? nums[idx2] : 0;
            tmpDp = tmp1 > tmp2 ? tmp1+nums[i] : tmp2+nums[i];
            nums[i] = tmpDp;
            max = Math.max(max, tmpDp);
        }
        return max;
    }
}
